Indirect branch prediction gives significant performance improvements to many programs. Indirect branch prediction utilizes tables which are also referred to as count caches since they are used to predict “branch to count instruction,” a form of indirect branch. For example, two tables storing information for indirect branch prediction can be implemented: a) a local count cache indexed by instruction address storing predicted targets, b) a global count cache indexed by a combination of instruction address and global history vector storing predicted targets, and c) a selector used to decide which of the two tables (local or global) will provide the indirect branch prediction target. The idea for having two tables is that a) the local table is used for relatively easy to predict branches—by predicting that the next target of a particular branch will be the same as the previous target of the branch, b) the global table is used to predict relatively difficult to predict branches—by predicting the next target based on a correlation of the branch address and the path taken (branch history vector), and c) the selector will decide which of the two strategies (local or global) applies better for a particular indirect branch.
The amount of information stored in these tables is however very significant, constraining the number of entries that can be put in these tables, because the full 62-bit target needs to be stored (the two low-order bits are always zero). Thus, the amount of storage for these tables is very significant, on the order of 32 Kbits for a table containing 512 entries. For comparison, direct branch prediction using a two-bit confidence counter and 16K entries will consume a similar amount of space.
Therefore, techniques for reducing the storage budget associated with indirect branch prediction would be desirable.